/*-------------------------------------------------------------------------
 *
 * pg_list.h
 *	  PostgreSQL 通用列表包的接口
 *
 * 曾几何时，Postgres 的部分代码是用 Lisp 编写，并使用真实的
 * cons-cell 列表作为主要数据结构。当这段代码被重写为 C 时，
 * 我们初期忠实地模拟了 cons-cell 列表，这无疑成了性能瓶颈。
 * 在几次重写之后，这些数据结构实际上变成了简单的可扩展数组；
 * 但是 "List" 这个名字和很多符号仍然保留。
 *
 * 对于原始实现的一个重要让步是，空列表总是由一个空指针表示（优先写为 NIL）。
 * 非空列表有一个头，其在列表保持非空时不会被重新定位，以及一个可扩展的数据数组。
 *
 * 我们支持三种类型的列表：
 *
 *	T_List: 指针列表
 *		（实际上通常指向节点的指针，但不总是；
 *		声明为 "void *"，以减少强制转换的麻烦）
 *	T_IntList: 整数列表
 *	T_OidList: Oid 列表
 *
 * （目前，整型和 Oid 的大小相同，但它们可能并不总是这样；
 * 尝试小心保持区分。）
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/nodes/pg_list.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef PG_LIST_H
#define PG_LIST_H

#include "nodes/nodes.h"


typedef union ListCell
{
	void	   *ptr_value;
	int			int_value;
	Oid			oid_value;
} ListCell;

typedef struct List
{
	NodeTag		type;			/* T_List, T_IntList 或 T_OidList */
	int			length;			/* 当前存在的元素数量 */
	int			max_length;		/* elements[] 的分配长度 */
	ListCell   *elements;		/* 可重新分配的单元数组 */
	/* 我们可能会和列表头一起分配一些单元： */
	ListCell	initial_elements[FLEXIBLE_ARRAY_MEMBER];
	/* 如果 elements == initial_elements，这不是单独的分配 */
} List;

/*
 * 唯一有效的空列表表示是 NIL；换句话说，
 * 非 NIL 列表保证长度 >= 1。
 */
#define NIL						((List *) NULL)

/*
 * 以下各种循环宏的状态结构。
 */
typedef struct ForEachState
{
	const List *l;				/* 我们正在循环的列表 */
	int			i;				/* 当前元素索引 */
} ForEachState;

typedef struct ForBothState
{
	const List *l1;				/* 我们正在循环的列表 */
	const List *l2;
	int			i;				/* 通用元素索引 */
} ForBothState;

typedef struct ForBothCellState
{
	const List *l1;				/* 我们正在循环的列表 */
	const List *l2;
	int			i1;				/* 当前元素索引 */
	int			i2;
} ForBothCellState;

typedef struct ForThreeState
{
	const List *l1;				/* 我们正在循环的列表 */
	const List *l2;
	const List *l3;
	int			i;				/* 通用元素索引 */
} ForThreeState;

typedef struct ForFourState
{
	const List *l1;				/* 我们正在循环的列表 */
	const List *l2;
	const List *l3;
	const List *l4;
	int			i;				/* 通用元素索引 */
} ForFourState;

typedef struct ForFiveState
{
	const List *l1;				/* 我们正在循环的列表 */
	const List *l2;
	const List *l3;
	const List *l4;
	const List *l5;
	int			i;				/* 通用元素索引 */
} ForFiveState;

/*
 * 这些例程足够小，且使用频率足够高，因此值得
 * 作为内联函数。
 */

/* 获取列表第一个单元的地址；如果空列表则为 NULL */
static inline ListCell *
list_head(const List *l)
{
	return l ? &l->elements[0] : NULL;
}

/* 获取列表最后一个单元的地址；如果空列表则为 NULL */
static inline ListCell *
list_tail(const List *l)
{
	return l ? &l->elements[l->length - 1] : NULL;
}

/* 获取列表的第二个单元的地址（如果有），否则为 NULL */
static inline ListCell *
list_second_cell(const List *l)
{
	if (l && l->length >= 2)
		return &l->elements[1];
	else
		return NULL;
}

/* 获取列表的长度 */
static inline int
list_length(const List *l)
{
	return l ? l->length : 0;
}

/*
 * 访问 List 单元内数据值的宏。
 *
 * 请注意，除了 "xxx_node" 宏外，这些都是
 * l值，可以被赋值。
 *
 * 注意：以前的 List API 版本留下了一个不幸的遗产：
 * 宏 lfirst() 被用来表示“此 cons 单元中的数据”。为了避免
 * 更改每个 lfirst() 的使用，这个意义得以保留。因此，
 * lfirst() 接受一个 ListCell 并返回它包含的数据；要获取
 * List 的第一个单元中的数据，请使用 linitial()。更糟糕的是，
 * lsecond() 与 linitial() 的关系比 lfirst() 更密切：
 * 针对一个 List，lsecond() 返回第二个列表单元中的数据。
 */
#define lfirst(lc)				((lc)->ptr_value)
#define lfirst_int(lc)			((lc)->int_value)
#define lfirst_oid(lc)			((lc)->oid_value)
#define lfirst_node(type,lc)	castNode(type, lfirst(lc))

#define linitial(l)				lfirst(list_nth_cell(l, 0))
#define linitial_int(l)			lfirst_int(list_nth_cell(l, 0))
#define linitial_oid(l)			lfirst_oid(list_nth_cell(l, 0))
#define linitial_node(type,l)	castNode(type, linitial(l))

#define lsecond(l)				lfirst(list_nth_cell(l, 1))
#define lsecond_int(l)			lfirst_int(list_nth_cell(l, 1))
#define lsecond_oid(l)			lfirst_oid(list_nth_cell(l, 1))
#define lsecond_node(type,l)	castNode(type, lsecond(l))

#define lthird(l)				lfirst(list_nth_cell(l, 2))
#define lthird_int(l)			lfirst_int(list_nth_cell(l, 2))
#define lthird_oid(l)			lfirst_oid(list_nth_cell(l, 2))
#define lthird_node(type,l)		castNode(type, lthird(l))

#define lfourth(l)				lfirst(list_nth_cell(l, 3))
#define lfourth_int(l)			lfirst_int(list_nth_cell(l, 3))
#define lfourth_oid(l)			lfirst_oid(list_nth_cell(l, 3))
#define lfourth_node(type,l)	castNode(type, lfourth(l))

#define llast(l)				lfirst(list_last_cell(l))
#define llast_int(l)			lfirst_int(list_last_cell(l))
#define llast_oid(l)			lfirst_oid(list_last_cell(l))
#define llast_node(type,l)		castNode(type, llast(l))

/*
 * 构建固定长度列表的便利宏
 */
#define list_make_ptr_cell(v)	((ListCell) {.ptr_value = (v)})
#define list_make_int_cell(v)	((ListCell) {.int_value = (v)})
#define list_make_oid_cell(v)	((ListCell) {.oid_value = (v)})

#define list_make1(x1) \
	list_make1_impl(T_List, list_make_ptr_cell(x1))
#define list_make2(x1,x2) \
	list_make2_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2))
#define list_make3(x1,x2,x3) \
	list_make3_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
					list_make_ptr_cell(x3))
#define list_make4(x1,x2,x3,x4) \
	list_make4_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
					list_make_ptr_cell(x3), list_make_ptr_cell(x4))
#define list_make5(x1,x2,x3,x4,x5) \
	list_make5_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
					list_make_ptr_cell(x3), list_make_ptr_cell(x4), \
					list_make_ptr_cell(x5))

#define list_make1_int(x1) \
	list_make1_impl(T_IntList, list_make_int_cell(x1))
#define list_make2_int(x1,x2) \
	list_make2_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2))
#define list_make3_int(x1,x2,x3) \
	list_make3_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
					list_make_int_cell(x3))
#define list_make4_int(x1,x2,x3,x4) \
	list_make4_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
					list_make_int_cell(x3), list_make_int_cell(x4))
#define list_make5_int(x1,x2,x3,x4,x5) \
	list_make5_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
					list_make_int_cell(x3), list_make_int_cell(x4), \
					list_make_int_cell(x5))

#define list_make1_oid(x1) \
	list_make1_impl(T_OidList, list_make_oid_cell(x1))
#define list_make2_oid(x1,x2) \
	list_make2_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2))
#define list_make3_oid(x1,x2,x3) \
	list_make3_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
					list_make_oid_cell(x3))
#define list_make4_oid(x1,x2,x3,x4) \
	list_make4_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
					list_make_oid_cell(x3), list_make_oid_cell(x4))
#define list_make5_oid(x1,x2,x3,x4,x5) \
	list_make5_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
					list_make_oid_cell(x3), list_make_oid_cell(x4), \
					list_make_oid_cell(x5))

/*
 * 定位列表的第n个单元格（从0开始计数）。
 * 如果没有这样的单元格，则会导致断言失败。
 */
static inline ListCell *
list_nth_cell(const List *list, int n)
{
	Assert(list != NIL);
	Assert(n >= 0 && n < list->length);
	return &list->elements[n];
}

/*
 * 返回非NIL列表中的最后一个单元格。
 */
static inline ListCell *
list_last_cell(const List *list)
{
	Assert(list != NIL);
	return &list->elements[list->length - 1];
}

/*
 * 返回指定列表中第n个元素包含的指针值（列表元素从0开始）。
 */
static inline void *
list_nth(const List *list, int n)
{
	Assert(IsA(list, List));
	return lfirst(list_nth_cell(list, n));
}

/*
 * 返回指定列表中第 n 个元素包含的整数值。
 */
static inline int
list_nth_int(const List *list, int n)
{
	Assert(IsA(list, IntList));
	return lfirst_int(list_nth_cell(list, n));
}

/*
 * 返回指定列表中第 n 个元素包含的 OID 值。
 */
static inline Oid
list_nth_oid(const List *list, int n)
{
	Assert(IsA(list, OidList));
	return lfirst_oid(list_nth_cell(list, n));
}

#define list_nth_node(type,list,n)	castNode(type, list_nth(list, n))

/*
 * 获取给定 ListCell 在给定 List 中的索引（从 0 开始）。
 */
static inline int
list_cell_number(const List *l, const ListCell *c)
{
	Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
	return c - l->elements;
}

/*
 * 获取列表 "l" 中 "c" 后一个单元的地址，如果没有则为 NULL。
 */
static inline ListCell *
lnext(const List *l, const ListCell *c)
{
	Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
	c++;
	if (c < &l->elements[l->length])
		return (ListCell *) c;
	else
		return NULL;
}

/*
 * foreach -
 *	  一个遍历列表的便利宏
 *
 * "cell" 必须是 "ListCell *" 变量的名称；它会指向
 * 每个 List 元素。正常退出循环后，"cell" 将为 NULL，
 * 但提前 "break" 将使其指向当前 List 元素。
 *
 * 小心在循环迭代时更改 List 对象。
 * 当前的语义是我们在每次迭代中检查连续的列表索引，
 * 因此插入或删除列表元素可能会导致元素被意外地重新访问或跳过。
 * 以前的 foreach() 实现行为不同。然而，安全地
 * 向列表追加元素（或一般地，在当前元素之后插入）是可以的；
 * 这样的新元素保证会被访问。同时，如果你使用
 * foreach_delete_current() 删除，当前 List 元素可以被删除。
 * 但是：这两种操作在当前迭代的剩余时间内都会使 "cell" 指针失效。
 */
#define foreach(cell, lst)	\
	for (ForEachState cell##__state = {(lst), 0}; \
		 (cell##__state.l != NIL && \
		  cell##__state.i < cell##__state.l->length) ? \
		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
		 (cell = NULL, false); \
		 cell##__state.i++)

/*
 * foreach_delete_current -
 *	  从与周围 foreach() 循环关联的 List 中删除当前列表元素，
 *	  返回新的 List 指针。
 *
 * 这等同于 list_delete_cell()，但它还调整 foreach
 * 循环的状态，以确保不会遗漏任何列表元素。 不要以其他方式
 * 从活动 foreach 循环的列表中删除元素！
 */
#define foreach_delete_current(lst, cell)	\
	(cell##__state.i--, \
	 (List *) (cell##__state.l = list_delete_cell(lst, cell)))

/*
 * foreach_current_index -
 *	  获取周围 foreach() 循环的当前元素的零基列表索引；传递 "ListCell *" 迭代变量的名称。
 *
 * 注意在调用 foreach_delete_current() 后使用该函数；此时值将与当前循环迭代的其余部分不同步。无论如何，由于您刚刚删除了当前元素，值基本上没有意义。
 */
#define foreach_current_index(cell)  (cell##__state.i)

/*
 * for_each_from -
 *	  类似于 foreach()，但从第 N 个（零基）列表元素开始，而不一定是第一个。
 *
 * N 超过列表长度是可以的，但不能为负数。
 *
 * 对 foreach() 的警告同样适用。
 */
#define for_each_from(cell, lst, N)	\
	for (ForEachState cell##__state = for_each_from_setup(lst, N); \
		 (cell##__state.l != NIL && \
		  cell##__state.i < cell##__state.l->length) ? \
		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
		 (cell = NULL, false); \
		 cell##__state.i++)

static inline ForEachState
for_each_from_setup(const List *lst, int N)
{
	ForEachState r = {lst, N};

	Assert(N >= 0);
	return r;
}

/*
 * for_each_cell -
 *	  一个便利宏，从指定的单元开始循环遍历列表。
 *
 * 对 foreach() 的警告同样适用。
 */
#define for_each_cell(cell, lst, initcell)	\
	for (ForEachState cell##__state = for_each_cell_setup(lst, initcell); \
		 (cell##__state.l != NIL && \
		  cell##__state.i < cell##__state.l->length) ? \
		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
		 (cell = NULL, false); \
		 cell##__state.i++)

static inline ForEachState
for_each_cell_setup(const List *lst, const ListCell *initcell)
{
	ForEachState r = {lst,
	initcell ? list_cell_number(lst, initcell) : list_length(lst)};

	return r;
}

/*
 * forboth -
 *	  一个便利宏，用于同时遍历两个链表。此宏同时遍历两个列表，当任一列表用尽元素时停止。根据调用位置的要求，可能还需要断言两个列表的长度相等。（但是，如果不相等，一些调用者依赖于结束单元值单独为 NULL 或非 NULL 的定义；不要试图对此进行优化。）
 *
 * 对 foreach() 的警告同样适用。
 */
#define forboth(cell1, list1, cell2, list2)							\
	for (ForBothState cell1##__state = {(list1), (list2), 0}; \
		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
		 (cell1 != NULL && cell2 != NULL); \
		 cell1##__state.i++)

#define multi_for_advance_cell(cell, state, l, i) \
	(cell = (state.l != NIL && state.i < state.l->length) ? \
	 &state.l->elements[state.i] : NULL)

/*
 * for_both_cell -
 *	  一个便利宏，循环遍历两个列表，从每个指定的单元开始。此宏同时遍历两个列表，当任一列表用尽元素时停止。根据调用位置的要求，可能还需要断言两个列表的长度相等，并且 initcell1 和 initcell2 在各自列表中处于相同位置。
 *
 * 对 foreach() 的警告同样适用。
 */
#define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2)	\
	for (ForBothCellState cell1##__state = \
			 for_both_cell_setup(list1, initcell1, list2, initcell2); \
		 multi_for_advance_cell(cell1, cell1##__state, l1, i1), \
		 multi_for_advance_cell(cell2, cell1##__state, l2, i2), \
		 (cell1 != NULL && cell2 != NULL); \
		 cell1##__state.i1++, cell1##__state.i2++)

static inline ForBothCellState
for_both_cell_setup(const List *list1, const ListCell *initcell1,
					const List *list2, const ListCell *initcell2)
{
	ForBothCellState r = {list1, list2,
		initcell1 ? list_cell_number(list1, initcell1) : list_length(list1),
	initcell2 ? list_cell_number(list2, initcell2) : list_length(list2)};

	return r;
}

/*
 * forthree -
 *	  三个列表的相同操作。
 */
#define forthree(cell1, list1, cell2, list2, cell3, list3) \
	for (ForThreeState cell1##__state = {(list1), (list2), (list3), 0}; \
		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
		 (cell1 != NULL && cell2 != NULL && cell3 != NULL); \
		 cell1##__state.i++)

/*
 * forfour -
 *	  四个列表的相同操作。
 */
#define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \
	for (ForFourState cell1##__state = {(list1), (list2), (list3), (list4), 0}; \
		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
		 multi_for_advance_cell(cell4, cell1##__state, l4, i), \
		 (cell1 != NULL && cell2 != NULL && cell3 != NULL && cell4 != NULL); \
		 cell1##__state.i++)

/*
 * forfive -
 *	  五个列表的相同操作。
 */
#define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \
	for (ForFiveState cell1##__state = {(list1), (list2), (list3), (list4), (list5), 0}; \
		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
		 multi_for_advance_cell(cell4, cell1##__state, l4, i), \
		 multi_for_advance_cell(cell5, cell1##__state, l5, i), \
		 (cell1 != NULL && cell2 != NULL && cell3 != NULL && \
		  cell4 != NULL && cell5 != NULL); \
		 cell1##__state.i++)

/* 位于 src/backend/nodes/list.c 的函数 */

extern List *list_make1_impl(NodeTag t, ListCell datum1);
extern List *list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2);
extern List *list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
							 ListCell datum3);
extern List *list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
							 ListCell datum3, ListCell datum4);
extern List *list_make5_impl(NodeTag t, ListCell datum1, ListCell datum2,
							 ListCell datum3, ListCell datum4,
							 ListCell datum5);

extern pg_nodiscard List *lappend(List *list, void *datum);
extern pg_nodiscard List *lappend_int(List *list, int datum);
extern pg_nodiscard List *lappend_oid(List *list, Oid datum);

extern pg_nodiscard List *list_insert_nth(List *list, int pos, void *datum);
extern pg_nodiscard List *list_insert_nth_int(List *list, int pos, int datum);
extern pg_nodiscard List *list_insert_nth_oid(List *list, int pos, Oid datum);

extern pg_nodiscard List *lcons(void *datum, List *list);
extern pg_nodiscard List *lcons_int(int datum, List *list);
extern pg_nodiscard List *lcons_oid(Oid datum, List *list);

extern pg_nodiscard List *list_concat(List *list1, const List *list2);
extern pg_nodiscard List *list_concat_copy(const List *list1, const List *list2);

extern pg_nodiscard List *list_truncate(List *list, int new_size);

extern bool list_member(const List *list, const void *datum);
extern bool list_member_ptr(const List *list, const void *datum);
extern bool list_member_int(const List *list, int datum);
extern bool list_member_oid(const List *list, Oid datum);

extern pg_nodiscard List *list_delete(List *list, void *datum);
extern pg_nodiscard List *list_delete_ptr(List *list, void *datum);
extern pg_nodiscard List *list_delete_int(List *list, int datum);
extern pg_nodiscard List *list_delete_oid(List *list, Oid datum);
extern pg_nodiscard List *list_delete_first(List *list);
extern pg_nodiscard List *list_delete_last(List *list);
extern pg_nodiscard List *list_delete_first_n(List *list, int n);
extern pg_nodiscard List *list_delete_nth_cell(List *list, int n);
extern pg_nodiscard List *list_delete_cell(List *list, ListCell *cell);

extern List *list_union(const List *list1, const List *list2);
extern List *list_union_ptr(const List *list1, const List *list2);
extern List *list_union_int(const List *list1, const List *list2);
extern List *list_union_oid(const List *list1, const List *list2);

extern List *list_intersection(const List *list1, const List *list2);
extern List *list_intersection_int(const List *list1, const List *list2);

/* 目前，list_intersection_ptr 等没有必要 */

extern List *list_difference(const List *list1, const List *list2);
extern List *list_difference_ptr(const List *list1, const List *list2);
extern List *list_difference_int(const List *list1, const List *list2);
extern List *list_difference_oid(const List *list1, const List *list2);

extern pg_nodiscard List *list_append_unique(List *list, void *datum);
extern pg_nodiscard List *list_append_unique_ptr(List *list, void *datum);
extern pg_nodiscard List *list_append_unique_int(List *list, int datum);
extern pg_nodiscard List *list_append_unique_oid(List *list, Oid datum);

extern pg_nodiscard List *list_concat_unique(List *list1, const List *list2);
extern pg_nodiscard List *list_concat_unique_ptr(List *list1, const List *list2);
extern pg_nodiscard List *list_concat_unique_int(List *list1, const List *list2);
extern pg_nodiscard List *list_concat_unique_oid(List *list1, const List *list2);

extern void list_deduplicate_oid(List *list);

extern void list_free(List *list);
extern void list_free_deep(List *list);

extern pg_nodiscard List *list_copy(const List *list);
extern pg_nodiscard List *list_copy_head(const List *oldlist, int len);
extern pg_nodiscard List *list_copy_tail(const List *list, int nskip);
extern pg_nodiscard List *list_copy_deep(const List *oldlist);

typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
extern void list_sort(List *list, list_sort_comparator cmp);

extern int	list_int_cmp(const ListCell *p1, const ListCell *p2);
extern int	list_oid_cmp(const ListCell *p1, const ListCell *p2);

#endif							/* PG_LIST_H */
